const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
        right: {
            val: "F",
        },
    },
};

function postorderTraversal(root) {
    let res = []
    let stack = []
    // 保存前一个访问的节点，用于确定当前节点的右子树是否访问完毕
    let prev = null
    while (root || stack.length) {
        // 找到最左侧节点
        while (root) {
            stack.push(root)
            root = root.left
        }
        // 将最左侧节点弹出
        let node = stack.pop()

        // 当没有右子树或者右子树已经访问完毕
        if (!node.right || node.right === prev) {
            res.push(node.val)
            // 记录前一节点
            prev = node
            // 将当前根节点标记为空
            root = null
        } else {
            // 右子树尚未访问完毕，将当前节点重新压入栈中
            stack.push(node)
            root = node.right
        }
    }
    return res
}

console.log(postorderTraversal(root));

var postorderTraversal2 = function(root) {
    let result = []
    let stack = []
    let cur = root
    let prev = null
    while(stack.length || cur) {
        if(cur) {
            stack.push(cur)
            cur = cur.left
        } else {
            let node = stack.pop()
            if(!node.right || node.right === prev) {
                result.push(node.val)
                prev = node
                cur = null
            } else {
                stack.push(node)
                cur = node.right
            }
        }
    }
    return result
};

console.log(postorderTraversal2(root));